package demo.practice.leetcode;

public class Trie2 {

    private final int ALPHABET_SIZE = 26;
    private  Trie2[] children= new Trie2[ALPHABET_SIZE];

    boolean isEndOfWord = false;
    public Trie2() {}


    /** Inserts a word into the trie. */
    public void insert(String word) {
        Trie2 current= this;
        for(int i=0;i<word.length();i++){
            char c = word.charAt(i);
            if(current.children[c-'a']==null){
                current.children[c-'a']= new Trie2();
            }
            current=current.children[c-'a'];
        }
        current.isEndOfWord=true;

    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie2 current= this;
        for(int i=0;i<word.length();i++){
            char c = word.charAt(i);
            if(current.children[c-'a']==null){
                return false;
            }
            current=current.children[c-'a'];
        }
        return current.isEndOfWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Trie2 current= this;
        for(int i=0;i<prefix.length();i++){
            char c = prefix.charAt(i);
            if(current.children[c-'a']==null){
                return false;
            }
            current=current.children[c-'a'];
        }
        return true;
    }
}
